package 两个节点的最近公共祖先;
import 相同的树.TreeNode;

import java.util.Stack;

class Solution {
    /*方法一:
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left != null && right != null){
            return root;
        }
        if (left != null){
            return left;
        }
        return right;
    }*/
    //方法二:
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //栈stackP存放root到p的路径
        Stack<TreeNode> stackP = new Stack<>();
        //获取root到p的路径,存到stackP中
        getPath(root,p,stackP);
        //栈stackQ存放root到q的路径
        Stack<TreeNode> stackQ = new Stack<>();
        //获取root到q的路径,存到stackQ中
        getPath(root,q,stackQ);
        //sizeP记录root到p路径长度
        int sizeP = stackP.size();
        //sizeQ记录root到q路径长度
        int sizeQ = stackQ.size();
        //如果两条路径长度不相等,将长的栈进行出栈,直到两条路径长度相等
        if (sizeP > sizeQ){
            int size = sizeP - sizeQ;
            while (size != 0){
                stackP.pop();
                size--;
            }
        }else {
            int size = sizeQ - sizeP;
            while (size != 0){
                stackQ.pop();
                size--;
            }
        }
        //stackP与stackQ同时进行出栈操作,直到栈顶元素相同
        while (stackP.peek() != stackQ.peek()){
            stackP.pop();
            stackQ.pop();
        }
        //此时两个栈的栈顶元素就是公共祖先
        return stackP.peek();
    }
    //获取root到node的路径,存放到stack中
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        //root为空返回假,说明没有路
        if(root == null){
            return false;
        }
        //将root入栈
        stack.push(root);
        //观察栈顶元素是不是要找的结点,如果是就说明路径到终点
        if (stack.peek() == node){
            return true;
        }
        //flg1记录root左树有没有node
        boolean flg1 = getPath(root.left,node,stack);
        if (flg1){
            return true;
        }
        //flg2记录root右树有没有node
        boolean flg2 = getPath(root.right,node,stack);
        if (flg2){
            return true;
        }
        //当前左右都不是node,将栈顶元素弹出
        stack.pop();
        return false;
    }
}